package Methods;

import java.util.ArrayList;

public class Interpolation {
	public static String lagrange(double[][] array) {
		String poly = "";
		double coef = 0;
		for (int i = 0; i < array.length; i++) {
			coef = array[i][1];
			for (int j = 0; j < array.length; j++) {
				if (i != j) {
					coef /= (array[i][0] - array[j][0]);
					poly += "(x" + (array[j][0] < 0 ? "+" : "-")
							+ Double.toString(Math.abs(array[j][0])) + ")*";
				}
			}
			poly += "(0" + (coef < 0 ? "-" : "+")
					+ Double.toString(Math.abs(coef)) + ")"
					+ (i == array.length - 1 ? "" : "+");
		}
		// System.out.println(poly);
		return poly;
	}

	public static String newtonDividedDifference(double[][] array) {
		String poly = "";
		ArrayList<Double> a0 = new ArrayList<Double>();
		ArrayList<Double> a1 = new ArrayList<Double>();

		for (int i = 0; i < array.length; i++) {
			a0.add(array[i][1]);
		}
		for (int i = 0; i < array.length - 1; i++) {
			a1.add((array[i + 1][1] - array[i][1])
					/ (array[i + 1][0] - array[i][0]));
		}
		@SuppressWarnings("unchecked")
		ArrayList<Double>[] table = new ArrayList[array.length];
		table[0] = a0;
		table[1] = a1;
		for (int i = 2; i < table.length; i++) {
			table[i] = new ArrayList<Double>();
			for (int j = 0; j < table.length - i; j++) {
				table[i].add((table[i - 1].get(j) - table[i - 1].get(j + 1))
						/ (array[j][0] - array[j + i][0]));
			}
		}
		for (int i = 0; i < table.length; i++) {
			for (int j = 0; j < i; j++) {
				poly += "(x" + (array[j][0] < 0 ? "+" : "-")
						+ Double.toString(Math.abs(array[j][0])) + ")*";
			}
			poly += "(0" + (table[i].get(0) < 0 ? "-" : "+")
					+ Double.toString(Math.abs(table[i].get(0))) + ")"
					+ (i == array.length - 1 ? "" : "+");
		}
		// System.out.println(poly);
		return poly;
	}
}
